//https://www.lintcode.com/problem/sparse-matrix-multiplication/description
// 654. 稀疏矩阵乘法
// 给定两个 稀疏矩阵 A 和 B，返回AB的结果。
// 您可以假设A的列数等于B的行数。

// 时间复杂度分析：
// 假设矩阵A，B均为 n x n 的矩阵，
// 矩阵A的稀疏系数为a，矩阵B的稀疏系数为b，
// a，b∈[0, 1]，矩阵越稀疏，系数越小。

// 方法一：暴力，不考虑稀疏性
// Time (n^2 * (1 + n)) = O(n^2 + n^3)
// Space O(1)

// 方法二：改进，仅考虑A的稀疏性
// Time O(n^2 * (1 + a * n) = O(n^2 + a * n^3)
// Space O(1)

// 方法三（最优）：进一步改进，考虑A与B的稀疏性
// Time O(n^2 * (1 + a * b * n)) = O(n^2 + a * b * n^3)
// Space O(b * n^2)

// 方法四：另外一种思路，将矩阵A, B非0元素的坐标抽出，对非0元素进行运算和结果累加
// Time O(2 * n^2 + a * b * n^4) = O(n^2 + a * b * n^4)
// Space O(a * n^2 + b * n^2)



class Solution {
public:
    /**
     * @param A: a sparse matrix
     * @param B: a sparse matrix
     * @return: the result of A * B
     */
    vector<vector<int>> multiply(vector<vector<int>> &A, vector<vector<int>> &B) {
        // 法一
        // • 常规实现时间复杂度
        // – O(mnk)  ≈  O(n 3 )
        int m = A.size();
        int n = B[0].size();
        int k = A[0].size();
        vector<vector<int>> result(m, vector<int>(n));
        // for (int i = 0; i < n; i++)
        // {
            // for (int j = 0; j < m; j++)
            // {
                // for (int t = 0; t < k; t++)
                // {
                    // result[j][i] += A[j][t] * B[t][i];
                // }
            // }
        // }
        // return result;
        
        // • 如果是稀疏 （很多0）的时候怎么办？以什么样的循环顺序？
        // – m  k  n  
        // for (int i = 0; i < m; i++)
        // {
        //     for (int j = 0; j < k; j++)
        //     {
        //         if (A[i][j] != 0)
        //         {
        //             for (int t = 0; t < n; t++)
        //             {
        //                 result[i][t] += B[j][t] * A[i][j];
        //             }
        //         }
        //     }
        // }
        // return result;
        
        // • 进一步优化:
        // 记录B的一行中非0元素的列数
        // • 优化后的时间复杂度
        // – O(nmt)  ≈  O(n 3 )
        // • 优化了什么
        // – 常数项时间
        
        int l = B.size();
        vector<vector<int>> record(l, vector<int>());
        for (int i = 0; i < l; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (B[i][j] != 0)
                {
                    record[i].push_back(j);
                }
            }
        }
        
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < k; j++)
            {
                if (A[i][j] != 0)
                {
                    for (int t = 0; t < record[j].size(); t++)
                    {
                        result[i][record[j][t]] += B[j][record[j][t]] * A[i][j];
                    }
                }
            }
        }
        
        return result;
    }
};